package com.mamingchao.basic.swardToOffer.three;

import com.google.common.collect.Lists;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 题目：完全二叉树的构造
 * 小红想构造一个总共n个节点的完全二叉树，该二叉树满足以下两个性质：
 * 1、所有节点的权值位1~n的一个排列
 * 2、除了根节点以外，每个节点的权值和父亲的权值乘积为偶数
 *
 * 输入描述：
 *     一个正整数 n，代表二叉树的节点数量
 *      2 <=n <= 10的5次方
 *
 * 输出描述：
 *     输入一行n个正整数，代表小红构造的二叉树的层序遍历的序列
 *
 * 设计方案：
 *      先用递归实现，然后优化成动态规划
 *
 * deep seek优化建议：
 *  1、起始的root节点，优先使用偶数（因为根没有父节点，选偶数可以简化子节点的约束）
 *  2、直接按层序遍历分配数字，优先使用偶数填充父节点，奇数填充子节点（如果父节点是奇数）。
 *
 *  最终方案
 *      根节点选偶数。
 *
 *      层序遍历填充：
 *          如果父节点是奇数，子节点必须是偶数。
 *          如果父节点是偶数，优先填充偶数，再用奇数。
 *      确保奇数尽量作为叶子节点。
 */
public class CompleteBinaryTree {

    public static void main(String[] args) {
        final  int n = 17;
        LinkedList<Integer> oddWeightPool = getWeightPool(n, true);
        LinkedList<Integer> evenWeightPool = getWeightPool(n, false);
//        int[] dp = getCompleteBinaryTreeRootNode(n, oddWeightPool, evenWeightPool);
        int[] dp1 = getCompleteBinaryTreeOptimize(n, oddWeightPool, evenWeightPool);
//        System.out.println(Arrays.toString(dp));
        System.out.println(Arrays.toString(dp1));
    }

    private static LinkedList<Integer> getWeightPool(int n, boolean isOdd) {
        LinkedList<Integer> weightPoll = Lists.newLinkedList();
        if (n < 2 ) {
            return weightPoll;
        }

        for (int i = 1; i < n + 1; i++) {
            if (isOdd && isOddNode(i)) {
                weightPoll.offerLast(i);
            } else if (!isOdd && !isOddNode(i)) {
                weightPoll.offerLast(i);
            }
        }
        return  weightPoll;
    }

    /**
     *
     * @param oddWeightPool 二叉树节点的偶数权值池
     * @param evenWeightPool 二叉树节点的奇数权值池
     * @return 返回完全二叉树 层序遍历的数组
     */
    public static int[] getCompleteBinaryTreeRootNode(int n, LinkedList<Integer> oddWeightPool, LinkedList<Integer> evenWeightPool){

        if (n < 2 || oddWeightPool.isEmpty() || evenWeightPool.isEmpty()) {
            return  new int[0];
        }

        LinkedList<Integer> oddWeightPoolFork = (LinkedList<Integer>)oddWeightPool.clone();
        LinkedList<Integer> evenWeightPoolFork =  (LinkedList<Integer>)evenWeightPool.clone();

        int[] dp = new int[n + 1];
        // case 1; // 优先使用偶数当根节点
        dp[1] = evenWeightPool.pollFirst();
        dp[2] = oddWeightPool.pollFirst();

        boolean choice1Worked  = refillDPArray(n, dp, oddWeightPool, evenWeightPool);
//        System.out.println(Arrays.toString(dp));
//        System.out.println("-----------------------------------------");

        // case 2;
        if (!choice1Worked) {
            dp[1] = oddWeightPoolFork.pollFirst();
            dp[2] = evenWeightPoolFork.pollFirst();

            refillDPArray(n, dp, oddWeightPoolFork, evenWeightPoolFork);
        }

        return dp;
    }

    /**
     * 优化版本，根节点优先使用偶数
     *
     * @param oddWeightPool 二叉树节点的偶数权值池
     * @param evenWeightPool 二叉树节点的奇数权值池
     * @return 返回完全二叉树 层序遍历的数组
     */
    public static int[] getCompleteBinaryTreeOptimize(int n, LinkedList<Integer> oddWeightPool, LinkedList<Integer> evenWeightPool){

        if (n < 2 || oddWeightPool.isEmpty() || evenWeightPool.isEmpty()) {
            return  new int[0];
        }

        int[] dp = new int[n + 1];
        // case 1; 优先使用偶数当跟节点
        dp[1] = evenWeightPool.pollFirst();

        boolean choice1Worked  = refillDPArray(n, dp, oddWeightPool, evenWeightPool);
        System.out.println(Arrays.toString(dp));
        System.out.println("-----------------------------------------");


        return dp;
    }


    private static boolean refillDPArray(int n, int[] dp, LinkedList<Integer> oddWeightPool, LinkedList<Integer> evenWeightPool) {
        boolean choiceWorked = true;
        for (int i = 2; i < n + 1; i++) {
            int rootIndex = i/2;
            // 如果父节点是奇数
            if (isOddNode(dp[rootIndex])) {
                int evenWeightValue = pollEvenWeightValue(evenWeightPool);
                if (evenWeightValue == 0) {
                    choiceWorked = false;
                    break;
                }
                dp[i] = evenWeightValue;
            } else {
                int oddWeightValue = pollOddWeightValue(oddWeightPool, evenWeightPool);
                if (oddWeightValue == 0) {
                    choiceWorked = false;
                    break;
                }
                dp[i] = oddWeightValue;
            }
        }
        return choiceWorked;
    }



    /**
     * 判断是否是基数
     * @param value
     * @return
     */
    private static boolean isOddNode(int value) {
        return  value % 2 == 1 ? true :false;
    }

    /**
     * 找偶数的权值；如果都没有，返回0
     *
     * @param evenWeightPool
     * @return
     */
    private static  int pollEvenWeightValue(LinkedList<Integer> evenWeightPool){
        if (!evenWeightPool.isEmpty()) {
            return evenWeightPool.pollFirst();
        }

        return 0;
    }

    /**
     * 获取奇数权值；优先找偶数的；如果偶数权值没了，则找技术的，如果都没有，返回0
     * @param oddWeightPool
     * @return
     */
    private static  int pollOddWeightValue(  LinkedList<Integer> oddWeightPool, LinkedList<Integer> evenWeightPool){
        if (!evenWeightPool.isEmpty()) {
            return evenWeightPool.pollFirst();
        }

        if (!oddWeightPool.isEmpty()) {
            return oddWeightPool.pollFirst();
        }

        return 0;
    }

}
